package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-10 18:21
 **/
public class LeetCode39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int size = candidates.length;
        List<List<Integer>> list = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        // 排序是剪枝的前提
        Arrays.sort(candidates);
        dfs(candidates, 0, size, target, list, path);
        return list;
    }

    void dfs(int[] candidates, int begin, int size, int target, List<List<Integer>> list, Deque<Integer> path) {
        if (target == 0) {
            list.add(new ArrayList<>(path));
        }

        for (int i = begin; i < size; i++) {
            //剪枝
            int number = target - candidates[i];
            if (number < 0) {
                break;
            }
            path.add(candidates[i]);
            dfs(candidates, i, size, number, list, path);
            path.removeLast();
        }
    }

    //dfs
    /*public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int size = candidates.length;
        List<List<Integer>> list = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(candidates, 0, size, target, list, path);
        return list;
    }

    void dfs(int[] candidates, int begin, int size, int target, List<List<Integer>> list, Deque<Integer> path) {
        if (target < 0) {
            return;
        }

        if (target == 0) {
            list.add(new ArrayList<>(path));
        }

        for (int i = begin; i < size; i++) {
            path.add(candidates[i]);
            dfs(candidates, i, size, target - candidates[i], list, path);
            path.removeLast();
        }
    }*/

}
